原始数据:表格、图片、视频、文本、语音、……
模型学习:最核心的部分,学习一个用来预测的映射
特征工程:
所有样本都有标记
| 原始数据 | 样本/示例 | 属性/特征 | 标记 |
|---|---|---|---|
| $o_1$ | $(\xv_1, y_1)$ | $[\xv_1]_{1:d}$ | $y_1$ |
| $o_2$ | $(\xv_2, y_2)$ | $[\xv_2]_{1:d}$ | $y_2$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $o_m$ | $(\xv_m, y_m)$ | $[\xv_m]_{1:d}$ | $y_m$ |
任务类型:
只有部分样本有标记,如何利用其它未标记样本?
| 原始数据 | 样本/示例 | 属性/特征 | 标记 |
|---|---|---|---|
| $o_1$ | $(\xv_1, y_1)$ | $[\xv_1]_{1:d}$ | $y_1$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $o_l$ | $(\xv_l, y_l)$ | $[\xv_m]_{1:d}$ | $y_l$ |
| $o_{l+1}$ | $(\xv_{l+1}, -)$ | $[\xv_{l+1}]_{1:d}$ | $-$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $o_{l+u}$ | $(\xv_{l+u}, -)$ | $[\xv_{l+u}]_{1:d}$ | $-$ |
任务类型:
所有样本都没有标记
| 原始数据 | 样本/示例 | 属性/特征 | 标记 |
|---|---|---|---|
| $o_1$ | $(\xv_1, -)$ | $[\xv_1]_{1:d}$ | $-$ |
| $o_2$ | $(\xv_2, -)$ | $[\xv_2]_{1:d}$ | $-$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $o_m$ | $(\xv_m, -)$ | $[\xv_m]_{1:d}$ | $-$ |
任务类型:
米哈尔斯基 等《机器学习:一种人工智能途径》
Machine Learning: An Artificial Intelligence Approach, 1983
费根鲍姆 等《人工智能手册》
The Handbook of Artificial Intelligence, 1983
多明戈斯 Pedro Domingos 《终极算法》
The Master Algorithm, 2015
灵魂问题:哪个算法更好?
| 次序 | 时间 | 方式 | 天气 | 课业 | 疫情 | 电视 | 约会 |
|---|---|---|---|---|---|---|---|
| 1 | 周六 | 吃饭 | 晴天 | 轻松 | 清零 | 精彩 | 是 |
| 6 | 周六 | 逛街 | 晴天 | 轻松 | 平缓 | 无聊 | 是 |
| 10 | 周六 | 学习 | 雨天 | 轻松 | 严峻 | 无聊 | 否 |
| 13 | 周六 | 逛街 | 晴天 | 适中 | 清零 | 精彩 | 否 |
| 14 | 周间 | 逛街 | 阴天 | 适中 | 清零 | 精彩 | ? |
| 次序 | 时间 | 方式 | 天气 | 课业 | 疫情 | 电视 | 约会 |
|---|---|---|---|---|---|---|---|
| 1 | 周六 | 吃饭 | 晴天 | 轻松 | 清零 | 精彩 | 是 |
| 6 | 周六 | 逛街 | 晴天 | 轻松 | 平缓 | 无聊 | 是 |
| 10 | 周六 | 学习 | 雨天 | 轻松 | 严峻 | 无聊 | 否 |
| 13 | 周六 | 逛街 | 晴天 | 适中 | 清零 | 精彩 | 否 |
| 14 | 周间 | 逛街 | 阴天 | 适中 | 清零 | 精彩 | ? |
用 if-then 形式的合取规则尽可能地概括正样本
$\text{是} \longleftarrow (\text{天气} = \text{晴天}) \wedge (\text{课业} = \text{轻松})$
| 次序 | 时间 | 方式 | 天气 | 课业 | 疫情 | 电视 | 约会 |
|---|---|---|---|---|---|---|---|
| 1 | 周六 | 吃饭 | 晴天 | 轻松 | 清零 | 精彩 | 是 |
| 6 | 周六 | 逛街 | 晴天 | 轻松 | 平缓 | 无聊 | 是 |
| 10 | 周六 | 学习 | 雨天 | 轻松 | 严峻 | 无聊 | 否 |
| 13 | 周六 | 逛街 | 晴天 | 适中 | 清零 | 精彩 | 否 |
| 14 | 周间 | 逛街 | 阴天 | 适中 | 清零 | 精彩 | ? |
用带阈值的线性函数 (感知机) 拟合数据
$\sign(w_0 + w_1 \cdot \text{次序} + \cdots + w_7 \cdot \text{电视}) \longrightarrow \{1, -1\}$
| 次序 | 时间 | 方式 | 天气 | 课业 | 疫情 | 电视 | 约会 |
|---|---|---|---|---|---|---|---|
| 1 | 周六 | 吃饭 | 晴天 | 轻松 | 清零 | 精彩 | 是 |
| 6 | 周六 | 逛街 | 晴天 | 轻松 | 平缓 | 无聊 | 是 |
| 10 | 周六 | 学习 | 雨天 | 轻松 | 严峻 | 无聊 | 否 |
| 13 | 周六 | 逛街 | 晴天 | 适中 | 清零 | 精彩 | 否 |
| 14 | 周间 | 逛街 | 阴天 | 适中 | 清零 | 精彩 | ? |
利用贝叶斯公式求后验概率
$\Pbb (\text{约会}|\text{次序},\text{时间},\ldots,\text{电视}) = \frac{\Pbb(\text{次序},\text{时间},\ldots,\text{电视}|\text{约会}) ~ \Pbb(\text{约会}) \quad \quad \quad ~~~~~}{\Pbb(\text{次序},\text{时间},\ldots,\text{电视}) \qquad \quad}$
| 次序 | 时间 | 方式 | 天气 | 课业 | 疫情 | 电视 | 约会 |
|---|---|---|---|---|---|---|---|
| 1 | 周六 | 吃饭 | 晴天 | 轻松 | 清零 | 精彩 | 是 |
| 6 | 周六 | 逛街 | 晴天 | 轻松 | 平缓 | 无聊 | 是 |
| 10 | 周六 | 学习 | 雨天 | 轻松 | 严峻 | 无聊 | 否 |
| 13 | 周六 | 逛街 | 晴天 | 适中 | 清零 | 精彩 | 否 |
| 14 | 周间 | 逛街 | 阴天 | 适中 | 清零 | 精彩 | ? |
引入相似度函数$s(\cdot, \cdot)$和样本权重$\alpha$
$\sign(\alpha_1 \cdot s(\xv_1, \xv_5) \cdot y_1 + \cdots + \alpha_4 \cdot s(\xv_4, \xv_5) \cdot y_4) \longrightarrow \{1,-1\}$
给定模型$f$、数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$
均方误差 (mean squared error, MSE)
$$ \begin{align*} \quad E_D (f) = \frac{1}{m} \sum_{i \in [m]} (f(\xv_i) - y_i)^2 \end{align*} $$
from sklearn.metrics import mean_squared_error y_true = [3, -0.5, 2, 7] y_pred = [2.5, 0.0, 2, 8] mean_squared_error(y_true, y_pred) # MSE 0.375 mean_squared_error(y_true, y_pred, squared=False) # RMSE 0.6123724356957945
给定模型$f$、数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$
错误率 (error rate)、精度 (accuracy)
$$ \begin{align*} \quad E_D (f) = \frac{1}{m} \sum_{i \in [m]} \Ibb (f(\xv_i) \ne y_i), ~ \acc(f;D) = 1 - E_D (f) \end{align*} $$
from sklearn.metrics import accuracy_score y_true = [0, 1, 2, 3] y_pred = [0, 2, 1, 3] accuracy_score(y_true, y_pred) # 百分比 0.5 accuracy_score(y_true, y_pred, normalize=False) # 正确分类的个数 2
二分类结果的混淆矩阵 (confusion matrix)
| 预测 正样本 | 实际 负样本 | |
|---|---|---|
| 真实 正样本 | $\TP$ (真正例) | $\FN$ (假反例) |
| 真实 负样本 | $\FP$ (假正例) | $\TN$ (真反例) |
查准率 (precision):预测的约会中有多少比例真的约会了
查全率 (recall):所有的约会中有多少比例被预测出来了
$$ \begin{align*} & \quad \mathrm{precision} = \frac{\TP}{\TP + \FP}, \quad \mathrm{recall} = \frac{\TP}{\TP + \FN} \\[4pt] & \quad \mathrm{F1} = \frac{2 \cdot \mathrm{precision} \cdot \mathrm{recall}}{\mathrm{precision} + \mathrm{recall}} = \frac{2 \cdot \TP}{\text{样本总数} + \TP - \TN \quad} \end{align*} $$
from sklearn.metrics import confusion_matrix from sklearn.metrics import precision_score, recall_score, f1_score y_true = [1, 1, 0, 0, 1, 0, 1, 0] y_pred = [0, 1, 0, 1, 1, 1, 1, 0] cm = confusion_matrix(y_true, y_pred, labels=[1,0]) cm [[3, 1], [2, 2]] tp, fn, fp, tn = cm.ravel() tp, fn, fp, tn (3, 1, 2, 2) precision_score(y_true, y_pred) 0.6 recall_score(y_true, y_pred) 0.75 f1_score(y_true, y_pred) 0.6666666666666665
终极目标:在未知数据上表现好,即泛化 (generalization) 好
样本空间$\Xcal \subset \Rbb^d$,标记空间$\Ycal$,$\Xcal \times \Ycal$上的未知概率分布$\Dcal$
给定模型$f$,训练数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$,其中$(\xv_i, y_i) \overset{\mathrm{iid}}{\sim} \Dcal$
几点说明:
回归:经验 (empirical) 均方误差、泛化均方误差分别为
$$ \begin{align*} \quad E_D (f) & = \frac{1}{m} \sum_{i \in [m]} (f(\xv_i) - y_i)^2 \\[4pt] \quad E_{\Dcal} (f) & = \Ebb_{(\xv,y) \sim \Dcal} [(f(\xv) - y)^2] = \Ebb_{D \sim \Dcal^m} [E_D (f)] \end{align*} $$
分类:经验错误率、泛化错误率分别为
$$ \begin{align*} \quad E_D (f) & = \frac{1}{m} \sum_{i \in [m]} \Ibb (f(\xv_i) \ne y_i) \\[4pt] \quad E_{\Dcal} (f) & = \Ebb_{(\xv,y) \sim \Dcal} [\Ibb(f(\xv) \ne y)] = \Ebb_{D \sim \Dcal^m} [E_D (f)] \end{align*} $$
在不致混淆的情况下,可统称为经验风险和泛化风险 (risk)
数据分布:$\Pbb(x) = \mathrm{U}[0,1]$,$\Pbb(y|x) = \cos (3 \pi x / 2) + \Ncal(0, 1) / 10$
学习算法:$n$阶多项式回归
$$ \begin{align*} \min_{w_j} ~ F (w_j) = \frac{1}{2} \sum_{i \in [m]} \left( \sum_{j=0}^n w_j x_i^j - y_i \right)^2 \end{align*} $$
其中$w_0, w_1, \ldots, w_n$为待求参数
目标函数$F$关于$w_j$的导数为
$$ \begin{align*} \nabla_{w_j} F = \sum_{i \in [m]} \left( \sum_{j=0}^n w_j x_i^j - y_i \right) x_i^j \end{align*} $$
左图:1 阶多项式欠拟合 (underfitting),经验均方误差很大
中图:4 阶多项式拟合地最好,最贴近真实模型 (groundtruth)
右图:30 阶多项式过拟合 (overfitting),经验均方误差很小
选对模型 (归纳偏好) 至关重要!如何选?
选对模型 (归纳偏好) 至关重要!如何选?
事先确定一组候选模型集合$\{ f_1, f_2, \ldots, f_n \}$,从中挑选最好的
从训练集中随机选择一部分样本作为验证集 (validation set)
交叉验证 (cross validation):将训练集平均分为$n$份,第$i$轮
遍历$i \in [n]$取平均作为$f_1, f_2, \ldots, f_n$的性能,从中挑选最好的
以回归问题为例,对任意样本$(\xv,y) \sim \Dcal$,均方误差可分解为
$$ \begin{align*} \quad (f (\xv) & - y)^2 = (f (\xv) - \Ebb [y|\xv] + \Ebb [y|\xv] - y)^2 \\ & = (f (\xv) - \Ebb [y|\xv])^2 + (\Ebb [y|\xv] - y)^2 + 2 (f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) \end{align*} $$
其中条件期望$\Ebb [y|\xv]$与$y$无关,对交叉项有
$$ \begin{align*} \quad \Ebb_{(\xv,y)} & [(f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) ] \\ & = \iint (f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) \Pbb(\xv, y) \diff \xv \diff y \\ & = \int (f (\xv) - \Ebb [y|\xv]) \left( \int (\Ebb [y|\xv] - y) \Pbb(\xv, y) \diff y \right) \diff \xv \\ & = \int (f (\xv) - \Ebb [y|\xv]) \underbrace{ ( \Ebb [y|\xv] \Pbb(\xv) - \Pbb(\xv) \overbrace{ \class{yellow}{\int y \Pbb(y|\xv) \diff y}}^{=~\Ebb [y|\xv]} )}_{=~0} \diff \xv = 0 \end{align*} $$
$$ \begin{align*} \quad \Ebb_{(\xv,y)} [(f (\xv) - y)^2] & = \Ebb_{(\xv,y)} [(\overbrace{f (\xv) - \Ebb [y|\xv]}^{\mathrm{independent~of~}y})^2] + \overbrace{\Ebb_{(\xv,y)} [(\Ebb [y|\xv] - y)^2]}^{\mathrm{noise~of~}y} \\ & = \Ebb_{\xv} [(f (\xv) - \Ebb [y|\xv])^2] + \noise \end{align*} $$
第二项标记中的噪声是问题所固有的,与模型$f$的选择无关
根据第一项,使得泛化均方误差最小的$f^\star (\xv) = \Ebb [y|\xv]$
数据集$D$的随机性也必须考虑进来,注意$\noise$与$D$无关,故
$$ \begin{align*} \quad E = \Ebb_D \Ebb_{(\xv,y)} [(f_D (\xv) & - y)^2] = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb [y|\xv])^2] + \noise \end{align*} $$
泛化均方误差$E = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb [y|\xv])^2] + \noise$
引入$\xv$的期望预测$\Ebb_D [f_D (\xv)]$,易知有分解
$$ \begin{align*} \quad (f_D (\xv) - \Ebb [y|\xv])^2 & = (f_D (\xv) - \Ebb_D [f_D (\xv)] + \Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2 \\ & = (f_D (\xv) - \Ebb_D [f_D (\xv)])^2 + (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2 \\ & \qquad + 2 (f_D (\xv) - \Ebb_D [f_D (\xv)]) (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]) \end{align*} $$
注意$\Ebb_D [f_D (\xv)]$与$D$无关,对交叉项有
$$ \begin{align*} \quad \Ebb_D [(f_D (\xv) - \Ebb_D [& f_D (\xv)]) (\overbrace{\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]}^{\mathrm{independent~of~}D})] \\ & = (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]) \underbrace{\Ebb_D [f_D (\xv) - \Ebb_D [f_D (\xv)]]}_{=~0} = 0 \end{align*} $$
$$ \begin{align*} E & = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2] + \Ebb_{\xv} \Ebb_D [(\overbrace{\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]}^{\mathrm{independent~of~}D})^2] + \noise \\ & = \underbrace{\Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2]}_{\variance} + \underbrace{\Ebb_{\xv} [(\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2]}_{\bias^2} + \noise \end{align*} $$
综上,泛化均方误差可分解为
$$ \begin{align*} \quad \Ebb_{(\xv,y)} \Ebb_D [(f_D (\xv) - y)^2] = \bias^2 + \variance + \noise \end{align*} $$
我们要选择低偏差同时低方差的模型!
偏差、方差往往是两难选择,即便对于单模型亦存在